1. Field of the Invention
This invention relates generally to image processing, and more particularly to a computer program for use with a general purpose computer that increases the efficiency of the general purpose computer as an image processor by reducing the number of memory accesses required.
2. Description of the Prior Art
A morphic transformation is an operation that maps a binary image into another binary image such that each picture element or pixel in the output image is some Boolean function of the corresponding pixel and other pixels in its neighborhood in the input image.
Even when the neighborhood is restricted to a pixel and the eight pixels adjacent to it horizontally, vertically and diagonally (a "3 by 3" or "Moore" neighborhood), morphic transformations are useful for many image processing and analysis operations. For example, Mandeville U.S. patent application Ser. No. 626,552, assigned to the assignee of the present invention, devised a generic method for detecting defects in images of printed circuit patterns that uses morphic transformations extensively.
Morphic transformations are also useful in other computer graphics operations. When applied to an image, morphic transformations permit manipulation of the image. For example, a morphic transformation of a curved line could remove all but the end points of the line. Another example would be use of a morphic transformation to strip away an outer layer of the image of an irregularly shaped object, or perhaps, add to it.
Due to its widespread usefulness, a number of special purpose hardware devices have been built to perform morphic transformations (see for example, Sternberg, U.S. Pat. No. 4,167,728) and Kimmel, U.S. Ser. No. 759,640 filed July 26,1985.
The present invention is a method and algorithm for performing morphic image transformations on a general purpose computer. Its principal advantage is that it runs faster than "conventional" algorithms because it reduces the number of memory accesses and other instructions.
To implement morphic transformations a nine bit convolution of the Moore Neighborhood may be performed. For purposes of explanation, pixel data having a value of 1 or 0, i.e on or off is considered. These techniques, are, however extendable to pixel data containing additional information, for example, color information. The convolution is performed by multiplying (weighting) each bit in the neighborhood by a predetermined amount, and adding the results together. If the predetermined weights are appropriately selected, for example, powers of 2 from 0 to 8, (2.sup.0, 2.sup.1, . . . 2.sup.8), the results, for each position will be a nine bit word that contains information relevant to the pixels of the Moore Neighborhood. The resulting nine bit word may then be operated on, for example using a look up table, to transform the image as required. Such convolutions require, for a Moore Neighborhood, a minimum of nine accesses to pixel memory to obtain the necessary data to be operated on.
In a general purpose computer, such memory accesses are usually quite slow, and consequently the morphic transformation is slow.